1. Field of the Invention
The present invention relates to bus arbitration and in particular to an improved method and associated apparatus for improving fairness in SCSI bus arbitration among a plurality of devices such as in a RAID storage subsystem.
2. Discussion of Related Art
When a plurality of devices are attached to a common electronic bus or other communication medium, multiple of the devices may simultaneously require use of the bus for exchange of signals. A method which determines which of several such competing devices is granted use of the common bus is often referred to as an arbitration method or simply bus arbitration.
A common bus arbitration method assigns a priority value or signal to each of the competing devices. The highest priority of the competing devices is first granted the bus, followed by other lesser priority devices. For example, in SCSI bus arbitration (as defined by the ANSI published SCSI 2 Standards Specification X3T9.2/375R Revision 10L), each device is assigned an ID value. When requesting the bus, each device applies a signal to the bus indicative of its priority and its desire to obtain the bus. Each device, so competing for the SCSI bus, determines whether any higher priority device (as determined by the device ID numeric value and the associated signal lines on the SCSI bus) is arbitrating for the SCSI bus. If a higher priority device is arbitrating for the SCSI bus (during the specified bus arbitration period), then the lower priority device will relinquish its request until the next arbitration period.
Under heavy bus utilization, such a priority based bus arbitration method will cause low priority devices on the bus to frequently lose the arbitration. The low priority devices will therefore suffer significant delays in reconnecting to complete their respective I/O operations. In RAID disk arrays, for example, a plurality of disk drives are aggregated and managed by a controller in such a manner as to appear as a single large, reliable disk. Information stored on such a disk array may be distributed across several of the disk drives in the disk array. A single I/O request directed to the disk array controller from an attached host computer system may therefore require low level I/O operations be performed on some or all of the disk drives in the disk array. The disk drives of the disk array may be distributed across a plurality of I/O channels (such as SCSI busses), but typical configurations share a single SCSI bus for several disk drives of the disk array. Since a single I/O request may involve several disk drives in the disk array, the performance of the RAID subsystem will be gated by the performance of the lowest priority disk drives in the shared bus. This problem is exacerbated by the addition of multiple RAID controllers concurrently processing I/O requests and the extension of SCSI standards to permit 14 devices per SCSI bus.
Priority based arbitration methods (as in the SCSI 2 specifications for example) are therefore unfair in their determination of which of a plurality of devices on the shared bus wins in arbitration. Higher priority devices will tend to preclude access to the bus for lower priority devices. The effects of this unfairness can be quantified by, for example, comparing the average delays for a SCSI reconnection to any disk drive in an array (averaged over all priorities) to the average delays incurred by reconnection of disk drives operable in accordance with an arbitration method adapted for improved fairness. It has been determined from such measurements that a fair arbitration method can improve the overall performance of a RAID subsystem by reducing the average I/O operation completion time. Such improvements can be especially beneficial where multiple RAID controllers are simultaneously generating I/O operations on one or more common SCSI busses filled to capacity with disk drives (a common configuration in most RAID subsystems).
However, prior methods for improving the fairness of arbitration have done so at a significant cost stemming from complexity of their solutions or performance costs arising from extension of the time for SCSI bus arbitration. Excessively extending the arbitration time reduces the RAID subsystem performance by adding idle time (the period of time during arbitration in which no data is transferred).
It can be seen from the above discussion that a need exists for improved arbitration techniques which improve fairness of the bus allocation while reducing time extensions of the bus arbitration cycle.